#ifndef _CXX_LIST_H
#define _CXX_LIST_H

namespace ds_cxx
{
template<typename T>
struct ListNode{
	T data;
	struct ListNode* next;
	struct ListNode* prev;
    ListNode(T data,struct ListNode* n=nullptr,struct ListNode* p=nullptr)
    : data(data),next(n),prev(p) {}
    ~ListNode(){ next = prev = nullptr;}
};

template<typename _Tp,bool _Dt = true>
struct _ListNodeIteratorBase{
    typedef _Tp  ValueType;
    typedef _Tp& Reference;
    typedef _Tp* Pointer;
    Reference operator*()
    {
        return _basePtr->data;
    }
    Pointer operator->()
    {
        return &_basePtr->data;
    }
    _ListNodeIteratorBase<_Tp,_Dt>& operator++()
    {
        _basePtr = _Dt ? _basePtr->next : _basePtr->prev;
        return *this;
    }
    _ListNodeIteratorBase<_Tp,_Dt>& operator++(int)
    {
        _basePtr = _Dt ? _basePtr->next : _basePtr->prev;
        return *this;
    }
    _ListNodeIteratorBase<_Tp,_Dt>& operator--()
    {
        _basePtr = _Dt ? _basePtr->prev : _basePtr->next;
        return *this;
    }
    _ListNodeIteratorBase<_Tp,_Dt>& operator--(int)
    {
        _basePtr = _Dt ? _basePtr->prev : _basePtr->next;
        return *this;
    }
    bool operator!=(const _ListNodeIteratorBase<_Tp,_Dt>& _ln)
    {
        return _ln._basePtr != _basePtr;
    }
    bool operator==(const _ListNodeIteratorBase<_Tp,_Dt>& _ln)
    {
        return _ln._basePtr == _basePtr;
    }
    _ListNodeIteratorBase(ListNode<_Tp>* _ptr) : _basePtr(_ptr){}
    ListNode<_Tp>* _basePtr;
};
    
#define ARRSET_HEAD(head) if(!head)\
{\
    head = new ListNodeT(T());\
    head->next = head;\
    head->prev = head;\
}

#define ARRSET_EMPTY(head,size) if(!head || size == 0 || head->next == head){ return ;}

template<typename T>
class List
{
public:
    typedef _ListNodeIteratorBase<T> Iterator;
    typedef _ListNodeIteratorBase<T,false> Reverse_Iterator;
    typedef ListNode<T>  ListNodeT;
    List() : head(nullptr),size(0)
    {
        head = new ListNodeT(T());
        head->next = head;
        head->prev = head;
    }
    ~List()
    {
        if(head)
        {
            ListNodeT* cur = head->next;
            while(cur != head)
            {
                ListNodeT* tmp = cur->next;
                delete(cur);
                cur = tmp;
            }
            delete(head);
            head = nullptr;
        }
    }
public:
    void PushBack(T& data)
    {
        ARRSET_HEAD(head)
        ListNodeT* node = new ListNodeT(data);
        ListNodeT* rear = head->prev;
        rear->next = node;
        node->prev = rear;
        node->next = head;
        head->prev = node;
        ++size;
    }
    void PushFront(T& data)
    {
        ARRSET_HEAD(head)
        ListNodeT* node = new ListNodeT(data);
        ListNodeT* front = head->next;
        head->next = node;
        node->prev = head;
        node->next = front;
        front->prev = node;
        ++size;
    }
    // pos before
    void Insert(T& data,int pos)
    {
        if(size < pos || pos < 0) return ; 
        ARRSET_HEAD(head)
        ListNodeT* cur = head;// dummy 0 1 2
        int k = pos;
        while(cur && (--k) > 0)
        {
            cur = cur->next;
        }
        ListNodeT* node = new ListNodeT(data);
        ListNodeT* nxt = cur->next;
        cur->next = node;
        node->prev = cur;
        node->next = nxt;
        nxt->prev = node;
        ++size;
    }
    void PopBack()
    {
        ARRSET_EMPTY(head,size)
        ListNodeT* rear = head->prev;
        rear->prev->next = head;
        head->prev = rear->prev;
        delete(rear);
        rear = nullptr;
        --size;
    }
    void PopFront()
    {
        ARRSET_EMPTY(head,size)
        ListNodeT* front = head->next;
        head->next = front->next;
        front->next->prev = head;
        delete(front);
        front = nullptr;
        --size;
    }
    void Erase(ListNodeT* node)
    {
        ARRSET_EMPTY(head,size)
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete(node);
        node = nullptr;
    }
    bool Exist(ListNodeT* node)
    {
        if(!head || size == 0 || !node) return false;
        ListNodeT* cur = head->next;
        while(cur && cur != head)
        {
            if(cur == node) return true;
            cur = cur->next;
        }
        return false;
    }
    T Front()
    {
        if(!head || size == 0 || head->next == head) return T();
        return head->next->data;
    }
    T Back()
    {
        if(!head || size == 0 || head->next == head) return T();
        return head->prev->data;
    }
    Iterator Begin()
    {
        return Iterator(!head ? nullptr : head->next);
    }
    Iterator End()
    {
        return Iterator(head);
    }
    Reverse_Iterator RBegin()
    {
        return Reverse_Iterator(!head ? nullptr : head->prev);
    }
    Reverse_Iterator REnd()
    {
        return Reverse_Iterator(head);
    }
    bool Empty() 
    {
        return size == 0;
    }
    unsigned int Length()
    {
        return size;
    }
    void Clear()
    {
        ListNodeT* cur = head->next;
        while(cur != head)
        {
            ListNodeT* tmp = cur->next;
            delete(cur);
            cur = tmp;
        }
        head->next = head;
        head->prev = head;
        size = 0;
    }
private:
    ListNodeT* head;
    unsigned int size;
};
}

#endif